package com.blb.suanfa;

/**
 * 查找算法
 */
public class SearchDemo {

    /**
     * 顺序查找 O（n)
     * @param array
     * @param number
     * @return
     */
    public static int orderSearch(int[] array,int number){
        for (int i = 0; i < array.length; i++) {
            if(array[i] == number){
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分查找 O（logN)
     * @param array
     * @param number
     * @return
     */
    public static int binarySearch(int[] array,int number){
        //定义左右两个下标
        int left = 0;
        int right = array.length - 1;
        //左右下标没重合就继续找
        while(left < right) {
            //找到中间数
            int middle = (left + right) / 2;
            //把中间数和要找的数比较
            if(array[middle] < number) {
                //中间数小淘汰前面的所有数
                left = middle + 1;
            }else if(array[middle] > number) {
                //中间数大淘汰后面的所有数
                right = middle - 1;
            }else{
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9,10};
        int position = binarySearch(array, 101);
        System.out.println("位置是：" + position);
    }
}
